#include "btree.h"

// 初始化二叉树
btree_t *btreeInit()
{
    btree_t *btree = malloc(sizeof(btree_t));
    if (btree == NULL)
    {
        printf("malloc btree failed\n");
        return NULL;
    }

    memset(btree, 0, sizeof(btree_t));

    return btree;
}

// 插入key值到二叉树中
btree_result_e btreeInsert(btree_t *btree, int key)
{
    // 1. 判断btree是否为空
    if (btree == NULL)
    {
        printf("btree is null\n");
        return BTREE_FAIL;
    }

    // 2. 判断key是否为空
    if (btree->key == key)
    {
        printf("key is exist\n");
        return BTREE_FAIL;
    }

    // 3. 判断key是否为空
    if (btree->key == 0)
    {
        btree->key = key;
        return BTREE_SUCCESS;
    }

    // 4. 判断柞树是否为空
    if (btree->left == NULL)
    {
        btree->left = malloc(sizeof(btree_t));
        if (btree->left == NULL)
        {
            printf("malloc btree->left failed\n");
            return BTREE_FAIL;
        }

        memset(btree->left, 0, sizeof(btree_t));
        btree->left->key = key;

        return BTREE_SUCCESS;
    }
    else
    {
        return btreeInsert(btree->left, key);
    }

    if (btree->right == NULL)
    {
        btree->right = malloc(sizeof(btree_t));
        if (btree->right == NULL)
        {
            printf("malloc btree->right failed\n");
            return BTREE_FAIL;
        }

        memset(btree->right, 0, sizeof(btree_t));
        btree->right->key = key;
        return BTREE_SUCCESS;
    }
    else
    {
        return btreeInsert(btree->right, key);
    }

    return BTREE_FAIL;
}

// 打印出所有节点的key值
btree_result_e btreePrint(btree_t *btree)
{
    if (btree == NULL)
    {
        printf("btree is null\n");
        return BTREE_FAIL;
    }

    if (btree->left != NULL)
    {
        btreePrint(btree->left);
        printf("btree->left = %d\n", btree->left->key);
    }

    if (btree->right != NULL)
    {
        btreePrint(btree->right);
        printf("btree->right = %d\n", btree->right->key);
    }

    printf("btree->key = %d\n", btree->key);
    return BTREE_SUCCESS;
}

// 销毁二叉树
btree_result_e btreeDestroy(btree_t *btree)
{
    if (btree == NULL)
    {
        printf("btree is null\n");
        return BTREE_FAIL;
    }

    if (btree->left != NULL)
    {
        btreeDestroy(btree->left);
        free(btree->left);
        btree->left = NULL;
    }

    if (btree->right != NULL)
    {
        btreeDestroy(btree->right);
        free(btree->right);
        btree->right = NULL;
    }

    free(btree);
    btree = NULL;
    return BTREE_SUCCESS;
}

// 查找key值是否存在
btree_result_e btreeFind(btree_t *btree, int key)
{
    if (btree == NULL)
    {
        printf("btree is null\n");
        return BTREE_FAIL;
    }
    if (btree->key == key)
    {
        printf("key is exist\n");
        return BTREE_SUCCESS;
    }

    if (btree->left != NULL)
    {
        btreeFind(btree->left, key);
        printf("btree->left = %d\n", btree->left->key);
        printf("-------------------------\n");
        return BTREE_SUCCESS;
    }

    if (btree->right != NULL)
    {
        btreeFind(btree->right, key);
        printf("btree->right = %d\n", btree->right->key);
        printf("-------------------------\n");
        return BTREE_SUCCESS;
    }

    printf("key is not exist\n");
    printf("-------------------------\n");
    return BTREE_FAIL;
}

// 删除key值
btree_result_e btreeDelete(btree_t *btree, int key)
{
    if (btree == NULL)
    {
        printf("btree is null\n");
        return BTREE_FAIL;
    }

    if (btree->key == key)
    {
        printf("key is exist\n");
        printf("btree->key = %d\n", btree->key);

        // 销毁该子节点及其子节点
        btreeDestroy(btree);
        return BTREE_SUCCESS;
    }

    if (btree->left != NULL)
    {
        return btreeDelete(btree->left, key);
    }

    if (btree->right != NULL)
    {
        return btreeDelete(btree->right, key);
    }

    printf("key is not exist\n");
    return BTREE_FAIL;
}

// 获取二叉树的高度
int btreeHeight(btree_t *btree)
{
    int leftHeight = 0;
    int rightHeight = 0;
    if (btree == NULL)
    {
        printf("btree is null\n");
        return BTREE_FAIL;
    }

    if (btree->left != NULL)
    {
        leftHeight = btreeHeight(btree->left);
    }
    if (btree->right != NULL)
    {
        rightHeight = btreeHeight(btree->right);
    }

    if (leftHeight > rightHeight)
    {
        return leftHeight + 1;
    }
    else
    {
        return rightHeight + 1;
    }

    return BTREE_SUCCESS;
}

int gap = 0, layout = 0;
// 图形化输出二叉树
void btreePrint2(btree_t *btree)
{
    if (btree == NULL)
    {
        printf("btree is null\n");
        return;
    }

    // 新的一行
    printf("└├ %d", btree->key);

    if (btree->left != NULL)
    {
        // printf("\n│\n├──");
        gap++;
        for (int i = 0; i < gap; i++)
        {
            printf(" ");
        }

        btreePrint2(btree->left);
    }

    if (btree->right != NULL)
    {
        // printf("\n│\n├──");
        gap++;
        for (int i = 0; i < gap; i++)
        {
            printf(" ");
        }
        btreePrint2(btree->right);
    }
    printf("\n");
}

int main(int argc, char *argv[])
{
    btree_t *btree = btreeInit();
    if (btree == NULL)
    {
        printf("btreeInit failed\n");
        return -1;
    }

    printf("btree = %#x\n", btree);

    for (int i = 0; i < 30; i++)
    {
        // 生成随机数填入其中
        int key = rand() % 10000;
        btreeInsert(btree, key);
    }

    // 获取数的高度
    int height = btreeHeight(btree);
    printf("height = %d\n", height);

    // 打印输出所有节点
    // printf("btreePrint2:\n");
    // btreePrint2(btree);

    // 销毁二叉树
    printf("btreeDestroy:\n");
    btreeDestroy(btree);

    return 0;
}
